package seqlist.link.leetcode;

/**
 * @author yuisama
 * @date 2023/03/19 15:22
 * 环的入口
 **/
public class Num142_DetectCycle {
    // 返回环形链表的入口节点
    public ListNode detectCycle(ListNode head) {
        // 结论 : 快慢指针相遇时，引入一个新的节点从链表头结点开始
        // 最终新节点一定会和慢指针在环的入口位置相遇
        ListNode low = head,fast = head;
        while (fast != null && fast.next != null) {
            low = low.next;
            fast = fast.next.next;
            if (low == fast) {
                ListNode third = head;
                while (third != low) {
                    low = low.next;
                    third = third.next;
                }
                return low;
            }
        }
        return null;
    }
}